Adjacency Matrix — Idea

A grid representing all possible edges.

• An adjacency matrix is an $n \times n$ grid, say `A`, where $n$ is the number of vertices. A value `A[i][j] = 1` indicates an edge from vertex $i$ to vertex $j$.
• This representation is excellent for dense graphs and provides a very fast, constant-time $O(1)$ lookup to check if an edge exists.
• A major drawback is its space requirement of $O(n^2)$, which can be very inefficient for sparse graphs with few edges.
• For undirected graphs, the matrix is always symmetric along its diagonal (i.e., `A[i][j] = A[j][i]`).

import numpy as np
V = ["A","B","C","D"]
index = {v:i for i,v in enumerate(V)}

A = np.zeros((4,4), dtype=int)

edges = [("A","B"), ("A","C"), ("B","D")]
for u,v in edges:
    i,j = index[u], index[v]
    A[i,j] = A[j,i] = 1  # Undirected symmetry

# A holds the final matrix